package 算法题;

/**
 * @time  2017/8/30
 * @Author jing
 */
/*
质数表的质数又称素数。指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。1和0既非素数也非合数。
素数举例：2 3 5 7 11 13 17 19 23 29

编程思想：
1、素数不可能是偶数(因为它能整除2)，所以只需要遍历奇数即可

2、通过规律发现，一个数只要不能整除[3,sqrt(N)]，就能判断它是一个素数
 */
public class 打印N以内的所有素数 {
    public static void main(String[] args) {
        //需要寻找的素数最大范围
        int num = 100;
        findSu(num);
    }

    private static void findSu(int num) {
        //排除意外情况
        if (num < 2) {
            System.out.println("[0," + num + "]没有素数");
            return;
        }
        if (num >= 2) {
            System.out.println("[0，"+num+"]的素数有：");
            System.out.println(2);
        }
        boolean toPrint; //控制是否打印当前数
        if (num > 2) {
            for (int i = 3; i < num; i += 2) { //遍历[3，num]内的所有奇数--可能为素数
                toPrint = true; //默认为素数，即要打印
                for (int j = 3; j <= Math.sqrt(i); j++) { //判断一个数是不是素数的除数
                    if (i % j == 0) {//i不是素数
                        toPrint = false; //不打印
                        break;
                    }
                }
                if (toPrint) {
                    System.out.println(i);
                }
            }
        }
    }
}
